In computer vision and image processing, an optical flow refers to measurements of moving objects between two consecutive image frames from a video sequence or a disparity between stereo pairs of images. Optical flow technologies are generally divided into two categories: sparse optical flow technologies and dense optical flow technologies.
Sparse optical flow technologies only provide motion vectors at particular locations of the image frames. These locations are often referred as “feature points”. Various feature point detection (or extraction) algorithms, such as Harris corner detector, difference of Gaussian, and determinant of Hessian matrix, can be used to determine the feature points. Each motion vector is a motion displacement between the feature points in one image frame and its corresponding position in the other image frame. Examples of feature-based sparse optical flow algorithms include Kanade-Lucas tracker (KLT), Scale Invariant Feature Transform (SIFT), Speed-Up Robust Features (SURF), Features from accelerated segment test (FAST), etc. Sparse optical algorithms' advantage is computation efficiency. However, a problem that they have is that they do not work as well as dense optical flow algorithms in many applications listed below.
Another of the categories of the optical flow technologies is the dense optical flow, which provides motion vectors at every pixel location in the image frames. The dense optical flow is very useful in many applications including, but not limited to, video denoising, video compression, object detection and tracking, motion segmentation, robotic navigation, or stereo disparity measurement.
For a dense optical flow computation, one of the optical flow algorithms is developed by Horn and Schunck. The algorithm developed by Horn and Schunck tries to optimize an objective function based on residuals from a brightness constancy constraint, and a particular regularization term expressing an expected smoothness of an optical flow field. Based on Horn and Schunck's general framework, many improvements have been made. However, one of the major disadvantages of Horn and Schunck's algorithm and similar algorithms is a problem of high computation complexity.
There are also existing so-called fast algorithms, such as Farnback, SimpleFlow, and DualTV L1. However, these algorithms have problems because the quality of a generated flow field is generally not satisfying and some of them may be even slower than the algorithm developed by Horn and Schunck. These algorithms are so-called fast because some of them are not very fast as pointed out below. Thus, there is a need for fast and high quality dense optical flow algorithms.
The embodiments subsequently describe the fast and high quality dense optical flow algorithms that solve the problems above by providing not only a less computation-intensive algorithm than those developed by Horn and Schunck but also a higher quality for optical flow field compared to the existing fast algorithms. Solutions to such problems have been long sought but prior developments have not taught or suggested any solutions and, thus, solutions to these problems have long eluded those skilled in the art.